package Test.offer;


import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @ClassName P32
 * @Description
 * @Company inspur
 * @Author Kevin
 * @Date 2020/8/1 12:55
 * @Version 1.0
 */
public class P32 {

    /**
     * 不分行从上往下打印二叉树
     */
    public void printTree1(BinaryTreeNode root) {
        if (root == null) {
            return;
        }

        Queue<BinaryTreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            BinaryTreeNode node = queue.poll();
            System.out.print(node.value + " ");
            if (node.left != null) {
                queue.add(node.left);
            }
            if (node.right != null) {
                queue.add(node.right);
            }
        }
    }

    /**
     * 分行从上往下打印二叉树
     */
    public void printTree2(BinaryTreeNode root) {
        if (root == null) return;

        Queue<BinaryTreeNode> queue = new LinkedList<>();
        queue.add(root);

        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size > 0) {
                BinaryTreeNode node = queue.poll();
                System.out.println(node.value + " ");
                if (node.left != null) queue.add(node.left);
                if (node.right != null) queue.add(node.right);
                size--;
            }
            System.out.println();
        }
    }



    /**
     * 之字形从上往下打印二叉树
     */
    public void printTree3(BinaryTreeNode root) {
        if (root == null) return;

        Stack<BinaryTreeNode> stack1 = new Stack<>();
        Stack<BinaryTreeNode> stack2 = new Stack<>();
        stack1.add(root);

        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                BinaryTreeNode node = stack1.pop();
                System.out.print(node.value + " ");
                if (node.left != null) stack2.add(node.left);
                if (node.right != null) stack2.add(node.right);
            }
            System.out.println();
            while (!stack2.isEmpty()) {
                BinaryTreeNode node = stack2.pop();
                System.out.print(node.value + " ");
                if (node.right != null) stack1.add(node.right);
                if (node.left != null) stack1.add(node.left);
            }
            System.out.println();
        }
    }

    class BinaryTreeNode {
        char value;
        BinaryTreeNode left;
        BinaryTreeNode right;

        public BinaryTreeNode(char value) {
            this.value = value;
        }
    }

}
